home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / standards / sgml / nist / parse2b / preproc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-13  |  12.4 KB  |  465 lines
  1. /* National Institute of Standards and Technology (NIST)
  2. /* National Computer System Laboratory (NCSL)
  3. /* Office Systems Engineering (OSE) Group
  4. /* ********************************************************************
  5. /*                            D I S C L A I M E R
  6. /*                              (March 8, 1989)
  7. /*  
  8. /* There is no warranty for the NIST NCSL OSE SGML parser and/or the NIST
  9. /* NCSL OSE SGML parser validation suite.  If the SGML parser and/or
  10. /* validation suite is modified by someone else and passed on, NIST wants
  11. /* the parser's recipients to know that what they have is not what NIST
  12. /* distributed, so that any problems introduced by others will not
  13. /* reflect on our reputation.
  14. /* 
  15. /* Policies
  16. /* 
  17. /* 1. Anyone may copy and distribute verbatim copies of the SGML source
  18. /* code as received in any medium.
  19. /* 
  20. /* 2. Anyone may modify your copy or copies of SGML parser source code or
  21. /* any portion of it, and copy and distribute such modifications provided
  22. /* that all modifications are clearly associated with the entity that
  23. /* performs the modifications.
  24. /* 
  25. /* NO WARRANTY
  26. /* ===========
  27. /* 
  28. /* NIST PROVIDES ABSOLUTELY NO WARRANTY.  THE SGML PARSER AND VALIDATION
  29. /* SUITE ARE PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER
  30. /* EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  31. /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  32. /* THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS
  33. /* WITH YOU.  SHOULD THE SGML PARSER OR VALIDATION SUITE PROVE DEFECTIVE,
  34. /* YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION.
  35. /* 
  36. /* IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW WILL NIST BE LIABLE FOR
  37. /* DAMAGES, INCLUDING ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL,
  38. /* INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR
  39. /* INABILITY TO USE (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA
  40. /* BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY THIRD PARTIES OR A
  41. /* FAILURE OF THE PROGRAM TO OPERATE WITH PROGRAMS NOT DISTRIBUTED BY
  42. /* NIST) THE PROGRAM, EVEN IF YOU HAVE BEEN ADVISED OF THE POSSIBILITY OF
  43. /* SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.
  44. */
  45.  
  46. /***************************************************************/
  47. /*    TITLE:          SGML PARSER                              */
  48. /*    SYSTEM:         DTD PREPROCESSOR                         */
  49. /*    SUBSYSTEM:      PREPROCESSOR for DETERMINING             */
  50. /*                       AMBIGUOUS CONTENT MODELS              */
  51. /*    SOURCE FILE:    PREPROC.C                                */
  52. /*    AUTHOR:         Steven Lindeman                          */
  53. /*    DATE CREATED:   05January1987                            */
  54. /***************************************************************/
  55.  
  56. /***************************************************************/
  57. /*   PREPROC -- Takes a valid content model to be reduced or   */
  58. /*              simplified and tokenizes it for use with       */
  59. /*              determin.c                                     */
  60. /***************************************************************/
  61. #include <stdio.h>
  62. #include <ctype.h>
  63. #include "detdefs.h"
  64. #include "detglbl.h"
  65.  
  66. void preproc(expression,buffer)
  67. char expression[];
  68. ITEM buffer[];
  69. {
  70.    int i,size,low,high,whocares;
  71.  
  72.    low = size = 0;  
  73.    high = -1;
  74.    init();
  75.    for (i=0; expression[i]!='\0'; i++)
  76.       high++;    /* set high */
  77.    whocares = reduce(expression,low,high,START);
  78.    tokenize(reducedexpr,buffer,&size);
  79. #ifdef JJJ
  80.    printf("Expression is -> %s\n",expression);
  81.    for (i=0; i<size; i++)
  82.       printf("%02d ",buffer[i].itoken);
  83.    printf("\n");
  84. #endif
  85.    return;
  86. }
  87.  
  88.  
  89. /***********************************/
  90. /* INIT                            */
  91. /***********************************/
  92. void init()
  93. {
  94.    int *iptr,i;
  95.  
  96.    symtabindx = 0;
  97.    memset((char *)buffer, '\0', sizeof(buffer));
  98.    for(i=0; i<BUFFSIZE; i++)
  99.       reducedexpr[i] = '\0';
  100.    index = 0;
  101. }
  102.  
  103. /***********************************/
  104. /* TOKENIZE                        */
  105. /***********************************/
  106. void tokenize(expression,buffer,j)
  107. char expression[];
  108. ITEM buffer[];
  109. int *j;
  110. {
  111.    int i,position;
  112.    char name[NAMELEN+1];
  113.  
  114.    i=0;
  115.  
  116.    while(expression[i] != '\0')  {
  117.       switch(expression[i])  {
  118.       case '(':     /* GRPO */
  119.          if (*j >= BUFFSIZE){
  120.             printf("overflow in preproc()\n");
  121.             exit(0);
  122.          }
  123.          buffer[(*j)++].itoken = GRPO;
  124.          break;
  125.       case ')':     /* GRPC */
  126.          if ((*j) >= BUFFSIZE){
  127.             printf("overflow in preproc()\n");
  128.             exit(0);
  129.          }
  130.          buffer[(*j)++].itoken = GRPC;
  131.          i++;   /* get next char */
  132.          handleoi(expression,buffer,&i,j);  /* tokenize occurr. ind. */
  133.          break;
  134.       case '&':
  135.       case '|':     /* AND, OR */
  136.          if ((*j) >= BUFFSIZE){
  137.             printf("overflow in preproc()\n");
  138.             exit(0);
  139.          }
  140.          buffer[(*j)++].itoken = OR;  /* AND must be converted to OR */
  141.          break;
  142.       case ',':     /* SEQ */
  143.          if ((*j) >= BUFFSIZE){
  144.             printf("overflow in preproc()\n");
  145.             exit(0);
  146.          }
  147.          buffer[(*j)++].itoken = SEQ;
  148.          break;
  149.       default:    /* must be a element name */
  150.          get_name(expression,&i,name); /* get element name */
  151.          position = mysearch(name);    /* find position */
  152.          if ((*j) >= BUFFSIZE){
  153.             printf("overflow in preproc()\n");
  154.             exit(0);
  155.          }
  156.          buffer[(*j)++].itoken = position+17;    /* tokenize name */
  157.          handleoi(expression,buffer,&i,j);  /* tokenize o.i. */
  158.          break;
  159.       }
  160.       i++;   /* next char */
  161.    }
  162.  
  163.    return;
  164. }
  165.  
  166. /*************************************/
  167. /* SEARCH                            */
  168. /*************************************/
  169. mysearch(name)
  170. char name[];
  171. {
  172.    int found,position;
  173.  
  174.  
  175.    found = FALSE;   
  176.    position=0;
  177.    while ((position < symtabindx) && (found != TRUE))  /* search table linearly */
  178.       if (strcmp(symtable[position].entry,name) == 0)
  179.          found = TRUE;   /* name was found */
  180.       else 
  181.          position++;
  182.    if (found == FALSE) {   /* not found in table */
  183.       strcpy(symtable[symtabindx].entry,name);   /* add to table */
  184.       symtabindx++;    /* increment index */
  185.    }
  186.  
  187.    return(position);   /* position found */
  188. }
  189.  
  190. /*************************************/
  191. /* GET_NAME                          */
  192. /*************************************/
  193. void get_name(expression,i,name)
  194. char expression[];
  195. int *i;
  196. char name[];
  197. {
  198.    int j;
  199.  
  200.    j = 0;
  201.  
  202.    while(isvalid(expression[*i]))
  203.       name[j++] = expression[(*i)++];   /* load name */
  204.    /* i will point to the next char */
  205.    name[j] = '\0';   /* null terminate */
  206.  
  207.    return;
  208. }
  209.  
  210. /*************************************/
  211. /* HANDLEOI                          */
  212. /*************************************/
  213. void handleoi(expression,buffer,i,j)
  214. char expression[];
  215. ITEM buffer[];
  216. int *i,*j;
  217. {
  218.    switch(expression[*i])  {
  219.    case '?':    /* OPT */
  220.       buffer[(*j)++].itoken = OPT;
  221.       break;
  222.    case '*':    /* REP  */
  223.       buffer[(*j)++].itoken = REP;
  224.       break;
  225.    case '+':   /* PLUS */
  226.       buffer[(*j)++].itoken = PLUS;
  227.       break;
  228.    default:  /* no oi, must add REQ */
  229.       buffer[(*j)++].itoken = REQ;
  230.       (*i)--;  /* unget char */
  231.       break;
  232.    }
  233.  
  234.    return;
  235. }
  236.  
  237. /*********************************/
  238. /* REMOVE_BLANKS *****************/
  239. /*********************************/
  240. void remove_blanks(newexpr,oldexpr)
  241. char newexpr[],oldexpr[];
  242. {
  243.    int i,j;
  244.  
  245.    i=j=0;
  246.  
  247.    while (oldexpr[i] != '\0')    /* not end of string */
  248.       if (oldexpr[i] != ' ')    /* not blank */
  249.          newexpr[j++] = oldexpr[i++];   /* copy char */
  250.       else 
  251.          i++;       /* incr i to skip blank */
  252.    newexpr[j] = '\0';   /* null newexpr */
  253.  
  254.    return;
  255. }
  256.  
  257. /*********************************/
  258. /* VALIDATE_EXPR *****************/
  259. /*********************************/
  260. void validate_expr(expr)
  261. char expr[];
  262. {
  263.    int i;
  264.  
  265.    i=0;
  266.  
  267.    while (expr[i] != '\0')  {  /* not end of string */
  268.       switch(expr[i])  {
  269.       case '(':
  270.       case ')':
  271.       case '+':
  272.       case '*':
  273.       case '?':
  274.       case ',':
  275.       case '|':
  276.       case '&':
  277.          break;
  278.       default:    /* must be a char or error */
  279.          if (!(isvalid(expr[i])))  {
  280.             printf("Illegal character in content model\n");
  281.             printf("Character -> '%c' , Character number %d\n",
  282.                 expr[i],i+1);
  283.             exit(99);
  284.          }
  285.          break;
  286.       }
  287.       i++;
  288.    }
  289.  
  290.    return;
  291. }
  292.  
  293. /********************************/
  294. /* GET_EXPR *********************/
  295. /********************************/
  296. get_expr(expr)
  297. char expr[];
  298. {
  299.    char temp[BUFFSIZE];
  300.    int length;
  301.  
  302.    length = get_string(temp,BUFFSIZE);
  303.    strcpy(expr,temp);         /* copy expr from temp */
  304.    remove_blanks(expr,temp);   /* remove blanks from expr */
  305.    validate_expr(expr);      /* validate expression */
  306.  
  307.    return(length);
  308. }
  309.  
  310. /********************************/
  311. /* GET_STRING *******************/
  312. /********************************/
  313. get_string(temp,size)
  314. char temp[];
  315. int size;
  316. {
  317.    int c,i;
  318.  
  319.    i = 0;
  320.  
  321.    while (--size > 0 && (c=getchar()) != EOF &&  c != '\n')
  322.       temp[i++] = c;
  323.    temp[i] = '\0';
  324.  
  325.    return(i);
  326. }
  327.  
  328. /********************************/
  329. /* REDUCE ***********************/
  330. /********************************/
  331. reduce(expr,low,high,came_from)
  332. char expr[];
  333. int low,high;
  334. int came_from;
  335. {
  336.    int i,scan,numstriped,level,reduced,startinsert;
  337.    int currentoi,newoi,saveoi;
  338.  
  339.    reduced = FALSE;
  340.    numstriped = 0;
  341.    saveoi = currentoi = '1';
  342.  
  343.    while (reduced == FALSE) {
  344.       level = 0;
  345.       for (scan=low; scan<=high; scan++)  { /* scan for connector at level==0 */
  346.          switch(expr[scan])  {
  347.          case '|':
  348.          case '&':
  349.          case ',':
  350.             if (level==0) {
  351.                startinsert = index;
  352.                currentoi = reduce(expr,low,scan-1,CONNECTOR);
  353.                reducedexpr[index++] = expr[scan];
  354.                currentoi = reduce(expr,scan+1,high,CONNECTOR);
  355.                currentoi = 1;
  356.                reduced = TRUE;
  357.                scan = high+1;
  358.                if (numstriped > 0)
  359.                   replace_parens(startinsert,saveoi);
  360.             }
  361.             break;
  362.          case '(':
  363.             level++;
  364.             break;
  365.          case ')':
  366.             level--;
  367.             break;
  368.          }
  369.       }
  370.       if (reduced == FALSE)
  371.          if (expr[high] == ')' || expr[high-1] == ')' )  {
  372.             if (expr[high] == ')' )  {
  373.                newoi = '1';
  374.                high--;
  375.             }
  376.             else
  377.                if (expr[high-1] == ')' )  {
  378.                   newoi = expr[high];
  379.                   high = high-2;
  380.                }
  381.             low++;
  382.             numstriped++;
  383.             update_oi(¤toi,newoi);
  384.             saveoi = currentoi;
  385.          }
  386.          else {    /* must be terminal */
  387.             switch(expr[high])  {
  388.             case '+':
  389.             case '?':
  390.             case '*':
  391.                newoi = expr[high--];   /* strip oi */
  392.                break;
  393.             default:
  394.                newoi = '1';
  395.                break;
  396.             }
  397.             update_oi(¤toi,newoi);
  398.             for (i=low; i<=high; i++)     /* add to reducedexpr  */
  399.                reducedexpr[index++] = expr[i];
  400.             if (numstriped > 0 && came_from == START)
  401.                replace_parens(0,currentoi);
  402.             if (currentoi != '1' && came_from == CONNECTOR)
  403.                reducedexpr[index++] = currentoi;
  404.             reduced = TRUE;
  405.          }
  406.    }
  407.    return(currentoi);
  408. }
  409. /**************************************/
  410. void replace_parens(insert,oi)
  411. int insert;
  412. char oi;
  413. {
  414.    int i;
  415.  
  416.    for (i=index; i>insert; i--)
  417.       reducedexpr[i] = reducedexpr[i-1];
  418.    index++;
  419.    reducedexpr[insert] = '(';
  420.    reducedexpr[index++] = ')';
  421.    if (oi != '1')
  422.       reducedexpr[index++] = oi;
  423.  
  424.    return;
  425. }
  426.  
  427. /*******************************************/
  428. /*   UPDATEOI                              */
  429. /*******************************************/
  430. void update_oi(currentoi, newoi)
  431. int *currentoi;
  432. char newoi;
  433. {
  434.    if (newoi == '+')
  435.       if ((*currentoi == '+') || (*currentoi == '1'))
  436.          *currentoi = '+';
  437.       else 
  438.          *currentoi = '*';
  439.    if (newoi == '?')
  440.       if ((*currentoi == '?') || (*currentoi == '1'))
  441.          *currentoi = '?';
  442.       else
  443.          *currentoi = '*';
  444.    if (newoi == '*')
  445.       *currentoi = '*';
  446.    return;
  447. }
  448. /*******************************************/
  449. /*   ISVALID                               */
  450. /*******************************************/
  451. int isvalid(c)
  452. char c;
  453. {
  454.    switch (c) {
  455.    case '.':
  456.    case '-':
  457.    case '#':
  458.       return(TRUE);
  459.    default:
  460.       if(isalnum(c))
  461.          return(TRUE);
  462.       return(FALSE);
  463.    }
  464. }
  465.